The activity of users on many social networking platforms largely comprises their interaction with different types of entities. For example, users follow other users (e.g. celebrities) on TWITTER or tag and comment on photos on FLICKR and FACEBOOK. These entities are at the core of many applications; they can be ranked in search results, recommended to users, or used in contextual advertising. Such applications assume knowledge of an entity's nature and characteristic attributes. An effective way to encode such knowledge is in the form of tags. An untagged entity is practically inaccessible, since it is hard to retrieve or interact with. Some platforms allow users to manually tag entities. However, even though such tags can be informative, they can oftentimes be inadequate, trivial or ambiguous. Numerous automated tagging methods have been proposed to address these issues. However, most of them require pre-existing high-quality tags or descriptive texts for every entity that needs to be tagged.